import "babel-polyfill";
import type from "../../type";
import {fastExponentation} from "../generic-algorithm";
import {ZeroDivisionError} from "../error";

const limb = 0x10000;
const block_mask = 0xffff;
const block_size = 16;
const template = "0123456789abcdefghijklmnopqrstuvwxyz";
const {isSafeInteger, isFinite} = Number;
const {abs, min, max, floor, sign, log, clz32, random} = Math;

var trim = function() {
    while (this.length && this[this.length - 1] === 0) {
        this.pop();
    }
    return this;
};

var group = function*(size) {
    var length = this.length;
    var offset = length % size;
    if (offset) {
        yield this.slice(0, offset);
    }
    for (let i = offset; i < length; i += size) {
        yield this.slice(i, i + size);
    }
};

export default class Integer {
    constructor(number, radix = 10) {
        if (arguments.length) {
            if (number instanceof Integer) {
                this._sign = number._sign;
                if (number._data) {
                    this._data = number._data;
                }
            } else if (type(number) === "Number") {
                if (isSafeInteger(number)) {
                    if (number > -limb && number < limb) {
                        this._sign = number;
                    } else {
                        this._sign = number * Infinity;
                        number = abs(number);
                        let data = [];
                        while (number) {
                            data.push(number & block_mask);
                            number = floor(number / limb);
                        }
                        this._data = data;
                    }
                } else {
                    throw new TypeError(`Invalid Number ${number}`);
                }
            } else if (type(number) === "String") {
                if (!number) {
                    throw new TypeError("Invalid String");
                }
                let string = number;
                let string_template = template.slice(0, radix);
                let sign = 1;
                if (number[0] === "+") {
                    number = number.slice(1);
                } else if (number[0] === "-") {
                    number = number.slice(1);
                    sign = -1;
                }
                let data = [];
                let exponent = floor(log(limb) / log(radix));
                let base = radix ** exponent;
                for (let l of number.toLowerCase()::group(exponent)) {
                    let n = 0;
                    for (let c of l) {
                        let index = string_template.indexOf(c);
                        if (index < 0) {
                            throw new TypeError(`Invalid String ${string}`);
                        }
                        n = n * radix + index;
                    }
                    for (let i = 0, length = data.length; i < length; ++i) {
                        n += data[i] * base;
                        data[i] = n & block_mask;
                        n >>>= block_size;
                    }
                    if (n) {
                        data.push(n);
                    }
                }
                if (data.length === 0) {
                    this._sign = 0;
                } else if (data.length === 1) {
                    this._sign = sign * data[0];
                } else {
                    this._sign = sign * Infinity;
                    this._data = data;
                }
            } else {
                throw new TypeError("Invalid Parameter Type");
            }
        } else {
            this._sign = 0;
        }
    }

    static from(n) {
        return n instanceof Integer ? n : new Integer(n);
    }

    static _create(sign, data) {
        var result = new Integer();
        result._sign = sign;
        if (data) {
            result._data = data;
        }
        return result;
    }

    static isInteger(n) {
        return n instanceof Integer || isSafeInteger(n);
    }

    get [Symbol.toStringTag]() {
        return "Integer";
    }

    get sign() {
        return this._sign;
    }

    toString(radix = 10) {
        var sign = this._sign;
        if (isFinite(sign)) {
            return sign.toString(radix);
        }
        var data = this._data.slice();
        var list = [];
        var exponent = floor(log(limb) / log(radix));
        var base = radix ** exponent;
        while (data.length) {
            let remainder = 0;
            for (let i = data.length; --i >= 0;) {
                remainder = (remainder << block_size) | data[i];
                data[i] = floor(remainder / base);
                remainder %= base;
            }
            list.push(remainder);
            data::trim();
        }
        var string = list.map(function(n) {
            var string_list = [];
            for (let i = 0; i < exponent; ++i) {
                string_list.push(n % radix);
                n = floor(n / radix);
            }
            return string_list.reverse().join("");
        }).reverse().join("").replace(/^0*/, "");
        if (sign < 0) {
            return "-" + string;
        } else {
            return string;
        }
    }

    static abs(n) {
        n = Integer.from(n);
        var sign = n._sign;
        if (sign >= 0) {
            return n;
        } else if (isFinite(sign)) {
            return Integer._create(-sign);
        } else {
            return Integer._create(Infinity, n._data);
        }
    }
    static negate(n) {
        n = Integer.from(n);
        var sign = n._sign;
        if (sign === 0) {
            return Integer.zero;
        } else {
            return Integer._create(-sign, n._data);
        }
    }

    static _array_compare(data1, data2, length, [offset1 = 0, offset2 = 0] = []) {
        for (let i = length; --i >= 0;) {
            let x = data1[i + offset1];
            let y = data2[i + offset2];
            if (x !== y) {
                return x - y;
            }
        }
        return 0;
    }

    static eq(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        if (m._sign !== n._sign) {
            return false;
        } else if (isFinite(m._sign)) {
            return true;
        }
        var data1 = m._data;
        var data2 = n._data;
        if (data1.length !== data2.length) {
            return false;
        }
        for (let i = 0, length = data1.length; i < length; ++i) {
            if (data1[i] !== data2[i]) {
                return false;
            }
        }
        return true;
    }
    static _absCompare(m, n) {
        if (abs(m._sign) !== abs(n._sign)) {
            return m._sign - n._sign;
        } else if (isFinite(m._sign)) {
            return 0;
        }
        var data1 = m._data;
        var data2 = n._data;
        if (data1.length !== data2.length) {
            return data1.length - data2.length;
        }
        for (let i = data1.length; --i >= 0;) {
            if (data1[i] !== data2[i]) {
                return data1[i] - data2[i];
            }
        }
        return 0;
    }
    static compare(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        if (m._sign !== n._sign) {
            return m._sign - n._sign;
        } else if (isFinite(m._sign)) {
            return 0;
        } else {
            return Integer._absCompare(m, n) * m._sign;
        }
    }

    static _add(data1, data2) {
        var result = [];
        if (data1.length < data2.length) {
            [data1, data2] = [data2, data1];
        }
        var temp = 0;
        for (let i = 0, l2 = data2.length; i < l2; ++i) {
            temp += data1[i] + data2[i];
            result.push(temp & block_mask);
            temp = temp > block_mask ? 1 : 0;
        }
        for (let i = data2.length, l1 = data1.length; i < l1; ++i) {
            temp += data1[i];
            result.push(temp & block_mask);
            temp = temp > block_mask ? 1 : 0;
        }
        if (temp) {
            result.push(temp);
        }
        return result;
    }
    static _addSingleLimb(data, n) {
        var result = [];
        var temp = n;
        for (let i = 0, l = data.length; i < l; ++i) {
            temp += data[i];
            result.push(temp & block_mask);
            temp = temp > block_mask ? 1 : 0;
        }
        if (temp) {
            result.push(temp);
        }
        return result;
    }

    static _subtract(data1, data2) {
        var result = [];
        var temp = 0;
        for (let i = 0, l2 = data2.length; i < l2; ++i) {
            temp += data1[i] - data2[i];
            result.push(temp & block_mask);
            temp = temp < 0 ? -1 : 0;
        }
        for (let i = data2.length, l1 = data1.length; i < l1; ++i) {
            temp += data1[i];
            result.push(temp & block_mask);
            temp = temp < 0 ? -1 : 0;
        }
        return result::trim();
    }
    static _subtractSingleLimb(data, n) {
        var result = [];
        var temp = -n;
        for (let i = 0, l = data.length; i < l; ++i) {
            temp += data[i];
            result.push(temp & block_mask);
            temp = temp < 0 ? -1 : 0;
        }
        return result::trim();
    }

    static add(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        var sign1 = m._sign;
        var sign2 = n._sign;
        if (sign1 === 0) {
            return n;
        } else if (sign2 === 0) {
            return m;
        } else if (isFinite(sign1) && isFinite(sign2)) {
            let result = sign1 + sign2;
            if (result > -limb && result < limb) {
                return Integer._create(result);
            } else {
                return Integer._create(result * Infinity, [abs(result) & block_mask, 1]);
            }
        }

        if (sign1 * sign2 > 0) {
            if (isFinite(sign1)) {
                return Integer._create(sign2, Integer._addSingleLimb(n._data, abs(sign1)));
            } else if (isFinite(sign2)) {
                return Integer._create(sign1, Integer._addSingleLimb(m._data, abs(sign2)));
            } else {
                return Integer._create(sign1, Integer._add(m._data, n._data));
            }
        } else {
            if (isFinite(sign1)) {
                let result = Integer._subtractSingleLimb(n._data, abs(sign1));
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(sign2));
                } else {
                    return Integer._create(sign2, result);
                }
            } else if (isFinite(sign2)) {
                let result = Integer._subtractSingleLimb(m._data, abs(sign2));
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(sign1));
                } else {
                    return Integer._create(sign1, result);
                }
            }
            let comparison = Integer._absCompare(m, n);
            if (comparison === 0) {
                return Integer.zero;
            } else if (comparison < 0) {
                let result = Integer._subtract(n._data, m._data);
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(sign2));
                } else {
                    return Integer._create(sign2, result);
                }
            } else {
                let result = Integer._subtract(m._data, n._data);
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(sign1));
                } else {
                    return Integer._create(sign1, result);
                }
            }
        }
    }

    static subtract(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        var sign1 = m._sign;
        var sign2 = n._sign;
        if (m._sign === 0) {
            return Integer.negate(n);
        } else if (n._sign === 0) {
            return m;
        } else if (isFinite(sign1) && isFinite(sign2)) {
            let result = sign1 - sign2;
            if (result > -limb && result < limb) {
                return Integer._create(result);
            } else {
                return Integer._create(result * Infinity, [abs(result) & block_mask, 1]);
            }
        }
        if (sign1 * sign2 > 0) {
            if (isFinite(sign1)) {
                let result = Integer._subtractSingleLimb(n._data, abs(sign1));
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(-sign2));
                } else {
                    return Integer._create(-sign2, result);
                }
            } else if (isFinite(sign2)) {
                let result = Integer._subtractSingleLimb(m._data, abs(sign2));
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(sign1));
                } else {
                    return Integer._create(sign1, result);
                }
            }
            let comparison = Integer._absCompare(m, n);
            if (comparison === 0) {
                return Integer.zero;
            } else if (comparison < 0) {
                let result = Integer._subtract(n._data, m._data);
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(-sign1));
                } else {
                    return Integer._create(-sign1, result);
                }
            } else {
                let result = Integer._subtract(m._data, n._data);
                if (result.length === 1) {
                    return Integer._create(result[0] * sign(sign1));
                } else {
                    return Integer._create(sign1, result);
                }
            }
        } else {
            if (isFinite(sign1)) {
                return Integer._create(-sign2, Integer._addSingleLimb(n._data, abs(sign1)));
            } else if (isFinite(sign2)) {
                return Integer._create(sign1, Integer._addSingleLimb(m._data, abs(sign2)));
            } else {
                return Integer._create(sign1, Integer._add(m._data, n._data));
            }
        }
    }

    static multiply(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        var sign1 = m._sign;
        var sign2 = n._sign;
        if (sign1 === 0 || sign2 === 0) {
            return Integer.zero;
        } else if (sign1 === 1) {
            return n;
        } else if (sign1 === -1) {
            return Integer.negate(n);
        } else if (sign2 === 1) {
            return m;
        } else if (sign2 === -1) {
            return Integer.negate(m);
        } else if (isFinite(sign1) && isFinite(sign2)) {
            let result = sign1 * sign2;
            if (result > -limb && result < limb) {
                return Integer._create(result);
            } else {
                let x = abs(result);
                return Integer._create(result * Infinity, [x & block_mask, x >>> block_size]);
            }
        }
        var data1 = m._data;
        var data2 = n._data;
        var result;
        if (isFinite(sign1)) {
            result = [];
            let m = abs(sign1);
            let temp = 0;
            for (let i = 0, l = data2.length; i < l; ++i) {
                temp += m * data2[i];
                result.push(temp & block_mask);
                temp >>>= block_size;
            }
            if (temp) {
                result.push(temp);
            }
        } else if (isFinite(sign2)) {
            result = [];
            let n = abs(sign2);
            let temp = 0;
            for (let i = 0, l = data1.length; i < l; ++i) {
                temp += n * data1[i];
                result.push(temp & block_mask);
                temp >>>= block_size;
            }
            if (temp) {
                result.push(temp);
            }
        } else {
            if (data1.length > data2.length) {
                [data1, data2] = [data2, data1];
            }
            let l1 = data1.length;
            let l2 = data2.length;
            result = new Array(l1 + l2).fill(0);
            for (let i = 0; i < l1; ++i) {
                let temp = 0;
                for (let j = 0; j < l2; ++j) {
                    temp += result[i + j] + data1[i] * data2[j];
                    result[i + j] = temp & block_mask;
                    temp >>>= block_size;
                }
                result[i + l2] = temp;
            }
            result::trim();
        }
        return Integer._create(sign1 * sign2, result);
    }
    static square(n) {
        n = Integer.from(n);
        var s = n._sign;
        if (s === 0 || s === 1) {
            return n;
        } else if (isFinite(s)) {
            let result = s * s;
            if (result < limb) {
                return Integer._create(result);
            } else {
                return Integer._create(result * Infinity, [result & block_mask, result >>> block_size]);
            }
        }
        var data = n._data;
        var length = data.length;
        var result = [];
        for (let i = 0; i < length; ++i) {
            let temp = data[i] ** 2;
            result.push(temp & block_mask, temp >>> block_size);
        }
        for (let i = 1; i < length; ++i) {
            for (let j = 0; j < i; ++j) {
                let temp = 2 * data[i] * data[j];
                for (let k = i + j; temp; ++k) {
                    temp += result[k];
                    result[k] = temp & block_mask;
                    temp = floor(temp / limb);
                }
            }
        }
        return Integer._create(Infinity, result::trim());
    }

    static _divide(m, n) {
        if (Integer._absCompare(m, n) < 0) {
            return [Integer.zero, m];
        } else if (isFinite(n._sign)) {
            n = n._sign;
            if (n === 1) {
                return [m, Integer.zero];
            } else if (isFinite(m._sign)) {
                m = m._sign;
                return [Integer._create(floor(m / n)), Integer._create(m % n)];
            }
            let data = m._data;
            if (data.length === 2 && data[1] < n) {
                m = data[1] * limb + data[0];
                return [Integer._create(floor(m / n)), Integer._create(m % n)];
            } else {
                let result = new Array(data.length);
                let temp = 0;
                for (let i = data.length; --i >= 0;) {
                    temp = temp * limb + data[i];
                    result[i] = floor(temp / n);
                    temp %= n;
                }
                return [Integer._create(Infinity, result::trim()), Integer._create(temp)];
            }
        }
        var top = n._data[n._data.length - 1];
        var shift = 0;
        while (top < (limb >>> 1)) {
            top <<= 1;
            ++shift;
        }
        m = Integer.shl(m, shift);
        n = Integer.shl(n, shift);
        var data1 = m._data.slice();
        var data2 = n._data;
        var length = data2.length;
        var offset = data1.length - length;
        var result = new Array(offset);
        var divisor = data2[length - 1] * limb + data2[length - 2];
        if (Integer._array_compare(data1, data2, length, [offset]) >= 0) {
            result.push(1);
            let temp = 0;
            for (let i = 0; i < length; ++i) {
                temp += data1[i + offset] - data2[i];
                data1[i + offset] = temp & block_mask;
                temp = temp < 0 ? -1 : 0;
            }
        }
        while (--offset >= 0) {
            let dividend = (data1[length + offset] * limb + data1[length - 1 + offset]) * limb + data1[length - 2 + offset];
            let quotient = max(min(block_mask, floor(dividend / divisor) - 1), 0);
            if (quotient >= 1) {
                let temp = 0;
                for (let i = 0; i < length; ++i) {
                    temp += data1[i + offset] - data2[i] * quotient;
                    data1[i + offset] = temp & block_mask;
                    temp = floor(temp / limb);
                }
                data1[length + offset] += temp;
            }
            if (data1[length + offset] || Integer._array_compare(data1, data2, length, [offset]) >= 0) {
                ++quotient;
                let temp = 0;
                for (let i = 0; i < length; ++i) {
                    temp += data1[i + offset] - data2[i];
                    data1[i + offset] = temp & block_mask;
                    temp = temp < 0 ? -1 : 0;
                }
                data1[length + offset] += temp;
            }
            result[offset] = quotient;
            data1.pop();
        }
        var quotient;
        if (result.length === 1) {
            quotient = Integer._create(result[0]);
        } else {
            quotient = Integer._create(Infinity, result);
        }
        if (data1::trim().length) {
            if (data1.length === 1) {
                return [quotient, Integer._create(data1[0] >>> shift)];
            } else {
                return [quotient, Integer.shr(Integer._create(Infinity, data1), shift)];
            }
        } else {
            return [quotient, Integer.zero];
        }
    }

    static _mod(m, n) {
        if (Integer._absCompare(m, n) < 0) {
            return m;
        } else if (isFinite(n._sign)) {
            n = n._sign;
            if (n === 1) {
                return Integer.zero;
            } else if (isFinite(m._sign)) {
                return Integer._create(m._sign % n);
            }
            let temp = 0;
            let data = m._data;
            for (let i = data.length; --i >= 0;) {
                temp = (temp * limb + data[i]) % n;
            }
            return Integer._create(temp);
        }
        var top = n._data[n._data.length - 1];
        var shift = 0;
        while (top < (limb >>> 1)) {
            top <<= 1;
            ++shift;
        }
        m = Integer.shl(m, shift);
        n = Integer.shl(n, shift);
        var data1 = m._data.slice();
        var data2 = n._data;
        var length = data2.length;
        var offset = data1.length - length;
        var divisor = data2[length - 1] * limb + data2[length - 2];
        if (Integer._array_compare(data1, data2, length, [offset]) >= 0) {
            let temp = 0;
            for (let i = 0; i < length; ++i) {
                temp += data1[i + offset] - data2[i];
                data1[i + offset] = temp & block_mask;
                temp = temp < 0 ? -1 : 0;
            }
        }
        while (--offset >= 0) {
            let dividend = (data1[length + offset] * limb + data1[length - 1 + offset]) * limb + data1[length - 2 + offset];
            let quotient = min(block_mask, floor(dividend / divisor) - 1);
            if (quotient >= 1) {
                let temp = 0;
                for (let i = 0; i < length; ++i) {
                    temp += data1[i + offset] - data2[i] * quotient;
                    data1[i + offset] = temp & block_mask;
                    temp = floor(temp / limb);
                }
                data1[length + offset] += temp;
            }
            if (data1[length + offset] || Integer._array_compare(data1, data2, length, [offset]) >= 0) {
                let temp = 0;
                for (let i = 0; i < length; ++i) {
                    temp += data1[i + offset] - data2[i];
                    data1[i + offset] = temp & block_mask;
                    temp = temp < 0 ? -1 : 0;
                }
                data1[length + offset] += temp;
            }
            data1.pop();
        }
        if (data1::trim().length) {
            if (data1.length === 1) {
                return Integer._create(data1[0] >>> shift);
            } else {
                return Integer.shr(Integer._create(Infinity, data1), shift);
            }
        } else {
            return Integer.zero;
        }
    }

    static divmod(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        var sign1 = m._sign;
        var sign2 = n._sign;
        if (sign2 === 0) {
            throw new ZeroDivisionError(`${m} / 0`);
        }
        var [quotient, remainder] = Integer._divide(Integer.abs(m), Integer.abs(n));
        if (remainder._sign === 0) {
            if (isFinite(quotient._sign)) {
                return [Integer._create(quotient._sign * sign(sign1 * sign2)), Integer.zero];
            } else {
                return [Integer._create(sign1 * sign2, quotient._data), Integer.zero];
            }
        } else if (sign1 * sign2 > 0) {
            if (isFinite(remainder._sign)) {
                return [quotient, Integer._create(remainder._sign * sign(sign2))];
            } else {
                return [quotient, Integer._create(sign2, remainder._data)];
            }
        } else {
            quotient = Integer.subtract(Integer[-1], quotient);
            if (sign2 < 0) {
                remainder = Integer.add(n, remainder);
            } else {
                remainder = Integer.subtract(n, remainder);
            }
            return [quotient, remainder];
        }
    }
    static divide(m, n) {
        return Integer.divmod(m, n)[0];
    }
    static mod(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        var sign1 = m._sign;
        var sign2 = n._sign;
        if (sign2 === 0) {
            throw new ZeroDivisionError(`${m} / 0`);
        }
        var remainder = Integer._mod(Integer.abs(m), Integer.abs(n));
        if (remainder._sign === 0) {
            return Integer.zero;
        } else if (sign1 * sign2 > 0) {
            if (isFinite(remainder._sign)) {
                return Integer._create(remainder._sign * sign(sign2));
            } else {
                return Integer._create(sign2, remainder._data);
            }
        } else {
            if (sign2 < 0) {
                remainder = Integer.add(n, remainder);
            } else {
                remainder = Integer.subtract(n, remainder);
            }
            return remainder;
        }
    }

    static exactDivide(m, n) {
        m = Integer.from(m);
        n = Integer.from(n);
        var sign1 = m._sign;
        var sign2 = n._sign;
        if (sign2 === 0) {
            throw new ZeroDivisionError(`${m} / 0`);
        } else if (sign1 === 0) {
            return Integer.zero;
        }
        var s;
        [s, n] = n.extractEven();
        m = Integer.shr(m, s);
        if (n._sign === 1) {
            return m;
        } else if (n._sign === -1) {
            return Integer.negate(m);
        }

        if (isFinite(n._sign)) {
            if (isFinite(m._sign)) {
                return m._sign / n._sign;
            } else {
                n = abs(n._sign);
                let data = m._data;
                let length = data.length;
                if (length <= 2 && data[1] < n) {
                    return Integer._create((data[1] * limb + data[0]) / n * sign(sign1 * sign2));
                }
                let result = new Array(length);
                let temp = 0;
                for (let i = length; --i >= 0;) {
                    temp = temp * limb + m._data[i];
                    result[i] = floor(temp / n);
                    temp %= n;
                }
                return Integer._create(sign1 * sign2, result::trim());
            }
        }
        var inverse = (function(last_digit) {
            var [m, n] = [last_digit, limb];
            var [a1, a2, b1, b2] = [0, 1, 1, 0];
            var q;
            while (m) {
                [[q, m], n] = [[floor(n / m), n % m], m];
                [a1, a2] = [a2, a1 - q * a2];
                [b1, b2] = [b2, b1 - q * b2];
            }
            return a1 & block_mask;
        })(n._data[0]);
        var result = [];
        var data1 = m._data.slice();
        var data2 = n._data;
        for (let i = 0, delta_length = data1.length - data2.length + 1; i < delta_length; ++i) {
            let quotient = (data1[i] * inverse) & block_mask;
            result.push(quotient);
            let temp = 0;
            if (quotient) {
                for (let j = 0, l2 = data2.length; j < l2; ++j) {
                    temp += data1[i + j] - data2[j] * quotient;
                    data1[i + j] = temp & block_mask;
                    temp = floor(temp / limb);
                }
                if (temp) {
                    data1[i + data2.length] += temp;
                }
            }
        }
        if (result::trim().length === 1) {
            return Integer._create(result[0] * sign(sign1 * sign2));
        } else {
            return Integer._create(sign1 * sign2, result);
        }
    }

    get bitLength() {
        if (isFinite(this._sign)) {
            return 32 - clz32(abs(this._sign));
        } else {
            let length = this._data.length;
            let n = this._data[length - 1];
            return (length - 1) * block_size + 32 - clz32(n);
        }
    }
    bit(n) {
        if (n < 0) {
            return 0;
        }
        var x;
        if (isFinite(this._sign)) {
            if (n > block_size) {
                return 0;
            }
            x = abs(this._sign);
        } else {
            if (n > (this._data.length * block_size)) {
                return 0;
            }
            x = this._data[n >>> 4];
        }
        n &= 0xf;
        return x & (1 << n) ? 1 : 0;
    }

    static pow(base, exponent, modulus) {
        base = Integer.from(base);
        if (modulus === undefined) {
            return fastExponentation(base, exponent, {
                multiply: Integer.multiply,
                square: Integer.square,
                one: Integer.one
            });
        } else {
            modulus = Integer.from(modulus);
            return fastExponentation(Integer.mod(base, modulus), exponent, {
                multiply: (m, n) => Integer.mod(Integer.multiply(m, n), modulus),
                square: n => Integer.mod(Integer.square(n), modulus),
                one: Integer.one
            });
        }
    }

    static shl(n, shift) {
        n = Integer.from(n);
        if (n._sign === 0 || shift === 0) {
            return n;
        }
        var result = new Array(floor(shift / block_size)).fill(0);
        shift %= block_size;
        var data = isFinite(n._sign) ? [abs(n._sign)] : n._data;
        if (shift === 0) {
            result = result.concat(data);
        } else {
            let temp = 0;
            for (let i = 0, l = data.length; i < l; ++i) {
                let x = data[i];
                result.push(((x << shift) & block_mask) | temp);
                temp = x >>> (block_size - shift);
            }
            if (temp) {
                result.push(temp);
            }
        }
        if (result.length === 1) {
            return Integer._create(result[0] * sign(n._sign));
        } else {
            return Integer._create(n._sign * Infinity, result);
        }
    }
    static shr(n, shift) {
        n = Integer.from(n);
        if (n.bitLength <= shift) {
            return Integer.zero;
        } else if (shift === 0) {
            return n;
        } else if (isFinite(n._sign)) {
            return Integer._create((abs(n._sign) >>> shift) * sign(n._sign));
        }
        var offset = floor(shift / block_size);
        shift %= block_size;
        var data = n._data;
        if (shift === 0) {
            var result = data.slice(offset);
        } else {
            var result = [];
            let temp = data[offset] >>> shift;
            for (let i = offset + 1, length = data.length; i < length; ++i) {
                result.push(((data[i] << (block_size - shift)) & block_mask) | temp);
                temp = data[i] >>> shift;
            }
            if (temp) {
                result.push(temp);
            }
        }
        if (result.length === 1) {
            return Integer._create(result[0] * sign(n._sign));
        } else {
            return Integer._create(n._sign * Infinity, result);
        }
    }

    extractEven() {
        if (this._sign === 0) {
            return [Infinity, 0];
        } else if (isFinite(this._sign)) {
            let n = abs(this._sign);
            let power = 0;
            if ((n & 0xff) === 0) {
                n >>>= 8;
                power += 8;
            }
            if ((n & 0xf) === 0) {
                n >>>= 4;
                power += 4;
            }
            if ((n & 3) === 0) {
                n >>>= 2;
                power += 2;
            }
            if ((n & 1) === 0) {
                n >>>= 1;
                ++power;
            }
            return [power, Integer._create(n * sign(this._sign))];
        }
        var offset = 0;
        var power = 0;
        var data = this._data;
        while (data[offset] === 0) {
            ++offset;
            power += block_size;
        }
        var n = data[offset];
        if ((n & 0xff) === 0) {
            n >>>= 8;
            power += 8;
        }
        if ((n & 0xf) === 0) {
            n >>>= 4;
            power += 4;
        }
        if ((n & 3) === 0) {
            n >>>= 2;
            power += 2;
        }
        if ((n & 1) === 0) {
            ++power;
        }
        return [power, Integer.shr(this, power)];
    }

    get lastLimb() {
        return isFinite(this._sign) ? abs(this._sign) : this._data[0];
    }

    static randomBits(bits) {
        var result = [];
        var blocks = floor(bits / block_size);
        bits %= block_size;
        for (let i = 0; i < blocks; ++i) {
            result.push(floor(random() * limb));
        }
        if (bits) {
            result.push(floor(random() * (1 << bits)));
        }
        if (result::trim().length) {
            if (result.length === 1) {
                return Integer._create(result[0]);
            } else {
                return Integer._create(Infinity, result);
            }
        } else {
            return Integer.zero;
        }
    }
    static random(n) {
        n = Integer.from(n);
        if (n._sign === 0) {
            return Integer.zero;
        } else if (isFinite(n._sign)) {
            return Integer._create(floor(random() * n._sign));
        }
        var bits = n.bitLength;
        var data = n._data;
        var length = data.length;
        var top = data[length - 1];
        if ((top & (top - 1)) === 0) {
            let ok = true;
            for (let i = 0; i < length - 1; ++i) {
                if (data[i] !== 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                --bits;
            }
        }
        while (true) {
            let result = Integer.randomBits(bits);
            if (Integer.compare(result, n) < 0) {
                return result;
            }
        }
    }
};

for (let i = -1024; i <= 1024; ++i) {
    Integer[i] = new Integer(i);
}

Integer.zero = Integer[0];
Integer.one = Integer[1];

export default Integer;

export var range = function*() {
    var start, stop, step;
    switch (arguments.length) {
    case 0:
        start = Integer.zero;
        step = Integer.one;
        break;
    case 1:
        start = Integer.zero;
        stop = arguments[0] === undefined ? undefined : Integer.from(arguments[0]);
        step = Integer.one;
        break;
    case 2:
        start = Integer.from(arguments[0]);
        stop = arguments[1] === undefined ? undefined : Integer.from(arguments[1]);
        step = Integer.one;
        break;
    case 3:
        start = Integer.from(arguments[0]);
        stop = arguments[1] === undefined ? undefined : Integer.from(arguments[1]);
        step = Integer.from(arguments[2]);
        break;
    }
    var compare;
    if (stop === undefined) {
        compare = () => true;
    } else if (step.sign > 0) {
        compare = n => Integer.compare(n, stop) < 0;
    } else {
        compare = n => Integer.compare(n, stop) > 0;
    }
    for (let n = start; compare(n); n = Integer.add(n, step)) {
        yield n;
    }
};
